/* 764. 最大加号标志 */
/**
 * @param {number} n
 * @param {number[][]} mines
 * @return {number}
 */

/* 
    对于每个中心点坐标（i，j） 分别从上下左右 四个方向
    计算（i，j） 开始最长连续1的个数 设dp[i][j][k] 表示
    以（i，j）为起点在方向k上的连续1的最大数目
    
    如果grid[i][j]为0 那么此时该方向的连续1的最大数目为0
    如果grid[i][j]为1 那么此时该方向的连续1的最大数数目为该
    方向上前一个单元为起点的数目+1


    假设 k = 0，1，2，3 分别表示 左 由 上 下 则地推公式如下：


    dp[i][j][0] = {
        0,    grid[i][j] = 0
        dp[i][j-1][0]+1, grid[i][j] = 1
    }
    dp[i][j][1] = {
        0,    grid[i][j] = 0
        dp[i][j+1][1]+1, grid[i][j] = 1
    } 
    dp[i][j][2] = {
        0,    grid[i][j] = 0
        dp[i-1][j][2]+1, grid[i][j] = 1
    } 
    dp[i][j][3] = {
        0,    grid[i][j] = 0
        dp[i+1][j][3]+1, grid[i][j] = 1
    } 
*/
var orderOfLargestPlusSign = function (n, mines) {
	const dp = new Array(n).fill(0).map(() => new Array(n).fill(n))
	const banned = new Set()
	for (const vec of mines) {
		banned.add(vec[0] * n + vec[1])
	}
	// console.log('banned :>>', banned)
	let ans = 0
	for (let i = 0; i < n; i++) {
		let count = 0
		/* left */
		for (let j = 0; j < n; j++) {
			if (banned.has(i * n + j)) {
				count = 0
			} else {
				count++
			}
			dp[i][j] = Math.min(dp[i][j], count)
		}
		count = 0
		/* right */
		for (let j = n - 1; j >= 0; j--) {
			if (banned.has(i * n + j)) {
				count = 0
			} else {
				count++
			}
			dp[i][j] = Math.min(dp[i][j], count)
		}
	}
	for (let i = 0; i < n; i++) {
		let count = 0
		/* up */
		for (let j = 0; j < n; j++) {
			if (banned.has(j * n + i)) {
				count = 0
			} else {
				count++
			}
			dp[j][i] = Math.min(dp[j][i], count)
		}
		count = 0
		/* down */
		for (let j = n - 1; j >= 0; j--) {
			if (banned.has(j * n + i)) {
				count = 0
			} else {
				count++
			}
			dp[j][i] = Math.min(dp[j][i], count)
			ans = Math.max(ans, dp[j][i])
		}
	}
	return ans
}
orderOfLargestPlusSign(5, [[4, 2]])
